use std::cmp::{max, min, Ordering};
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::Hash;
use std::i64;
use std::marker::PhantomData;
use std::mem::zeroed;
use std::ops::{Add, Neg};
use std::ptr::{write, NonNull};

use crate::collections::common::SearchTreeBase;

#[derive(PartialEq, Copy, Clone)]
pub enum TraverseOrd {
    PreOrd,
    MidOrd,
    PostOrd,
    LevelOrd,
    LeavesOrd,
}

#[derive(PartialEq, Copy, Clone)]
pub enum Color {
    Red,
    Black,
}

impl Neg for Color {
    type Output = Color;

    fn neg(self) -> Self::Output {
        match self {
            Color::Red => Color::Black,
            Color::Black => Color::Red,
        }
    }
}

#[derive(PartialEq, Copy, Clone)]
pub enum ThreadField {
    Child,
    Thread,
}

#[derive(PartialEq, Copy, Clone)]
pub enum AVLFactor {
    MinusMinus,
    Minus,
    Zero,
    Plus,
    PlusPlus,
}

impl Add for AVLFactor {
    type Output = AVLFactor;

    fn add(self, rhs: Self) -> Self::Output {
        match (self, rhs) {
            (lhs, AVLFactor::Zero) => lhs,
            (AVLFactor::Zero, rhs) => rhs,
            (AVLFactor::Minus, AVLFactor::Plus) => AVLFactor::Zero,
            (AVLFactor::Plus, AVLFactor::Minus) => AVLFactor::Zero,
            (AVLFactor::Minus, AVLFactor::Minus) => AVLFactor::MinusMinus,
            (AVLFactor::Plus, AVLFactor::Plus) => AVLFactor::PlusPlus,
            _ => panic!("the caculation result is not permitted"),
        }
    }
}

pub trait BNodeBase<T> {
    fn create(val: T) -> Box<Self>;

    fn set_value(&mut self, val: T);

    fn value(&self) -> T;

    fn set_left(&mut self, left: Option<NonNull<Self>>);

    fn left(&self) -> Option<NonNull<Self>>;

    fn set_right(&mut self, right: Option<NonNull<Self>>);

    fn right(&self) -> Option<NonNull<Self>>;

    fn set_parent(&mut self, parent: Option<NonNull<Self>>);

    fn parent(&self) -> Option<NonNull<Self>>;

    fn is_leaf(&self) -> bool {
        self.left().is_none() && self.right().is_none()
    }

    fn unwrap(self: Box<Self>) -> T {
        self.value()
    }
}

pub trait WeightedBNodeBase<T>: BNodeBase<T> {
    fn set_weight(&mut self, weight: i64);

    fn weight(&self) -> i64;

    fn cmp(&self, other: &Self) -> Ordering {
        self.weight().cmp(&other.weight())
    }

    fn heavier(&self, other: &Self) -> bool {
        self.weight() > other.weight()
    }

    fn lighter(&self, other: &Self) -> bool {
        self.weight() < other.weight()
    }

    fn equals(&self, other: &Self) -> bool {
        self.weight() == other.weight()
    }
}

pub trait BTreeBase<T> {
    fn new() -> Self;

    fn append(&mut self, val: T);

    fn delete(&mut self, val: T);

    fn clear(&mut self);

    fn size(&self) -> u64;

    fn leaves(&self) -> u64;

    fn min(&self) -> Option<T>;

    fn max(&self) -> Option<T>;

    fn find_by<F: FnMut(T) -> bool>(&self, f: F) -> Vec<T>;

    fn traverse<F, U>(&mut self, f: F, order: TraverseOrd) -> Vec<U>
    where
        F: FnMut(T) -> U;
}

pub trait BinarySearchNodeBase<K: Ord, V>: BNodeBase<V> {
    fn set_key(&mut self, key: K);

    fn key(&self) -> K;

    fn cmp_with_key(&self, key: &K) -> Ordering {
        self.key().cmp(key)
    }

    fn cmp(&self, other: &Self) -> Ordering {
        self.key().cmp(&other.key())
    }

    fn greater(&self, other: &Self) -> bool {
        self.key() > other.key()
    }

    fn less(&self, other: &Self) -> bool {
        self.key() < other.key()
    }

    fn equals(&self, other: &Self) -> bool {
        self.key() == other.key()
    }

    fn grandparent(&self) -> Option<NonNull<Self>> {
        if let Some(par) = self.parent() {
            unsafe {
                return (*par.as_ptr()).parent();
            }
        }
        None
    }

    fn sibling(&self) -> Option<NonNull<Self>> {
        unsafe {
            if let Some(par) = self.parent() {
                match (*par.as_ptr()).left() == Some(self.into()) {
                    true => (*par.as_ptr()).right(),
                    false => (*par.as_ptr()).left(),
                }
            } else {
                None
            }
        }
    }

    fn uncle(&self) -> Option<NonNull<Self>> {
        unsafe {
            if let Some(gpar) = self.grandparent() {
                match self.parent() == (*gpar.as_ptr()).left() {
                    true => (*gpar.as_ptr()).right(),
                    false => (*gpar.as_ptr()).left(),
                }
            } else {
                None
            }
        }
    }

    fn rotate_left(&mut self) {
        unsafe {
            if let Some(par) = self.parent() {
                if (*par.as_ptr()).right() == Some(self.into()) {
                    // L0
                    (*par.as_ptr()).set_right(self.left());
                    if let Some(left) = self.left() {
                        (*left.as_ptr()).set_parent(self.parent());
                    }
                    // L1
                    self.set_parent((*par.as_ptr()).parent());
                    if let Some(grandpar) = self.parent() {
                        match (*grandpar.as_ptr()).left() == Some(par) {
                            true => (*grandpar.as_ptr()).set_left(Some(self.into())),
                            false => (*grandpar.as_ptr()).set_right(Some(self.into())),
                        }
                    }
                    self.set_left(Some(par));
                    (*par.as_ptr()).set_parent(Some(self.into()));
                }
            }
        }
    }

    fn rotate_right(&mut self) {
        unsafe {
            if let Some(par) = self.parent() {
                if (*par.as_ptr()).left() == Some(self.into()) {
                    // L0
                    (*par.as_ptr()).set_left(self.right());
                    if let Some(right) = self.right() {
                        (*right.as_ptr()).set_parent(self.parent());
                    }
                    // L1
                    self.set_parent((*par.as_ptr()).parent());
                    if let Some(grandpar) = self.parent() {
                        match (*grandpar.as_ptr()).left() == Some(par) {
                            true => (*grandpar.as_ptr()).set_left(Some(self.into())),
                            false => (*grandpar.as_ptr()).set_right(Some(self.into())),
                        }
                    }
                    self.set_right(Some(par));
                    (*par.as_ptr()).set_parent(Some(self.into()));
                }
            }
        }
    }

    fn in_order_traverse<B, F: FnMut(K, V) -> Option<B>>(&mut self, dst: &mut Vec<B>, f: &mut F) {
        unsafe {
            if let Some(left) = self.left() {
                (*left.as_ptr()).in_order_traverse(dst, f);
            }
            if let Some(val) = f(self.key(), self.value()) {
                dst.push(val);
            }
            if let Some(right) = self.right() {
                (*right.as_ptr()).in_order_traverse(dst, f);
            }
        }
    }
}

pub trait ThreadedAVLNodeBase<K: Ord, V>: BinarySearchNodeBase<K, V> + BNodeBase<V> {
    fn balance_factor(&self) -> AVLFactor;

    fn update_factor(&mut self, factor: AVLFactor);

    fn set_left_with_field(&mut self, left: Option<NonNull<Self>>, field: ThreadField);

    fn set_right_with_field(&mut self, right: Option<NonNull<Self>>, field: ThreadField);

    fn left_field(&self) -> ThreadField;

    fn right_field(&self) -> ThreadField;

    fn is_balance(&self) -> bool {
        self.balance_factor() == AVLFactor::Zero
    }

    fn thread_rotate_left(&mut self) {
        unsafe {
            if let Some(par) = self.parent() {
                if (*par.as_ptr()).right() == Some(self.into()) {
                    // L0
                    if self.left_field() == ThreadField::Thread {
                        self.set_left_with_field(Some(par), ThreadField::Child);
                        (*par.as_ptr())
                            .set_right_with_field(Some(self.into()), ThreadField::Thread);
                    } else {
                        self.set_left(Some(par));
                        (*par.as_ptr()).set_right(self.left());
                        if let Some(left) = self.left() {
                            (*left.as_ptr()).set_parent(self.parent());
                        }
                    }
                    // L1
                    self.set_parent((*par.as_ptr()).parent());
                    if let Some(grandpar) = self.parent() {
                        match (*grandpar.as_ptr()).left() == Some(par) {
                            true => (*grandpar.as_ptr()).set_left(Some(self.into())),
                            false => (*grandpar.as_ptr()).set_right(Some(self.into())),
                        }
                    }
                    (*par.as_ptr()).set_parent(Some(self.into()));
                }
            }
        }
    }

    fn thread_rotate_right(&mut self) {
        unsafe {
            if let Some(par) = self.parent() {
                if (*par.as_ptr()).left() == Some(self.into()) {
                    // L0
                    if self.right_field() == ThreadField::Thread {
                        self.set_right_with_field(Some(par), ThreadField::Child);
                        (*par.as_ptr()).set_left_with_field(Some(self.into()), ThreadField::Thread);
                    } else {
                        self.set_right(Some(par));
                        (*par.as_ptr()).set_left(self.right());
                        if let Some(right) = self.right() {
                            (*right.as_ptr()).set_parent(self.parent());
                        }
                    }
                    // L1
                    self.set_parent((*par.as_ptr()).parent());
                    if let Some(grandpar) = self.parent() {
                        match (*grandpar.as_ptr()).left() == Some(par) {
                            true => (*grandpar.as_ptr()).set_left(Some(self.into())),
                            false => (*grandpar.as_ptr()).set_right(Some(self.into())),
                        }
                    }
                    (*par.as_ptr()).set_parent(Some(self.into()));
                }
            }
        }
    }
}

pub trait RedBlackNodeBase<K: Ord, V>: BinarySearchNodeBase<K, V> + BNodeBase<V> {
    fn color(&self) -> Color;

    fn examine_after_insert(&mut self);

    fn examine_after_delete(&mut self);

    fn repigment(&mut self);

    fn null_node() -> Box<Self> {
        let val: V = unsafe { zeroed() };
        let mut boxed = Self::create(val);
        boxed.repigment();
        boxed
    }

    fn delete_and_examine(&mut self) {
        unsafe {
            // suppose that the node has at most one non-null child and parent
            let virtual_child = match self.right().is_none() {
                true => self.left(),
                false => self.right(),
            };
            // create a node as NIL
            let child = match virtual_child {
                Some(c) => c,
                None => Box::leak(Self::null_node()).into(),
            };
            let parent = self.parent().unwrap();
            (*child.as_ptr()).set_parent(Some(parent));
            match (*parent.as_ptr()).left() == Some(self.into()) {
                true => (*parent.as_ptr()).set_left(Some(child)),
                false => (*parent.as_ptr()).set_right(Some(child)),
            }
            if self.color() == Color::Black {
                if (*child.as_ptr()).color() == Color::Red {
                    (*child.as_ptr()).repigment();
                } else {
                    (*child.as_ptr()).examine_after_delete();
                }
            }
            if virtual_child.is_none() {
                // delete the child
                if let Some(parent) = (*child.as_ptr()).parent() {
                    match (*parent.as_ptr()).left() == Some(child) {
                        true => (*parent.as_ptr()).set_left(None),
                        false => (*parent.as_ptr()).set_right(None),
                    }
                    Box::from_raw(child.as_ptr());
                }
            }
        }
    }
}

pub trait TreeIterator<N, T> {
    fn size(&self) -> u64;

    fn enumerate(&mut self) -> (u64, Option<NonNull<N>>);

    fn next(&mut self) -> Option<NonNull<N>> {
        self.enumerate().1
    }

    fn nth(&mut self, mut n: u64) -> Option<NonNull<N>>
    where
        T: Sized + Clone,
        N: BNodeBase<T>,
    {
        while let Some(x) = self.next() {
            if n == 0 {
                return Some(x);
            }
            n -= 1;
        }
        None
    }

    fn map<B, F>(mut self, mut f: F) -> Vec<B>
    where
        T: Sized + Clone,
        N: BNodeBase<T>,
        F: FnMut(T) -> B,
        Self: Sized,
    {
        let mut res = Vec::<B>::with_capacity(self.size() as usize);
        while let Some(x) = self.next() {
            unsafe {
                let value = (*x.as_ptr()).value();
                res.push(f(value));
            }
        }
        res
    }

    fn for_each<B, F>(mut self, mut f: F)
    where
        T: Sized + Clone,
        N: BNodeBase<T>,
        F: FnMut(T) -> T,
        Self: Sized,
    {
        while let Some(x) = self.next() {
            let ptr = x.as_ptr();
            unsafe {
                (*ptr).set_value(f((*ptr).value()));
            }
        }
    }

    fn find<P>(mut self, mut p: P) -> Option<NonNull<N>>
    where
        T: Sized + Clone,
        N: BNodeBase<T>,
        P: FnMut(T) -> bool,
        Self: Sized,
    {
        while let Some(x) = self.next() {
            unsafe {
                if p((*x.as_ptr()).value()) {
                    return Some(x);
                }
            }
        }
        None
    }

    fn filter<P>(mut self, mut p: P) -> Vec<NonNull<N>>
    where
        T: Sized + Clone,
        N: BNodeBase<T>,
        P: FnMut(T) -> bool,
        Self: Sized,
    {
        let mut res = Vec::<NonNull<N>>::with_capacity(self.size() as usize);
        while let Some(x) = self.next() {
            unsafe {
                if p((*x.as_ptr()).value()) {
                    res.push(x);
                }
            }
        }
        res
    }

    fn fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        T: Sized + Clone,
        N: BNodeBase<T>,
        F: FnMut(B, T) -> B,
        Self: Sized,
    {
        let mut accum = init;
        while let Some(x) = self.next() {
            accum = f(accum, unsafe { (*x.as_ptr()).value() });
        }
        accum
    }
}

pub struct BNode<T> {
    value: T,
    parent: Option<NonNull<BNode<T>>>,
    left: Option<NonNull<BNode<T>>>,
    right: Option<NonNull<BNode<T>>>,
}

impl<T: Clone> BNodeBase<T> for BNode<T> {
    #[inline]
    fn create(val: T) -> Box<Self> {
        Box::new(BNode {
            value: val,
            parent: None,
            left: None,
            right: None,
        })
    }

    #[inline]
    fn value(&self) -> T {
        self.value.clone()
    }

    #[inline]
    fn set_value(&mut self, val: T) {
        unsafe { write(&mut self.value, val) }
    }

    #[inline]
    fn left(&self) -> Option<NonNull<Self>> {
        self.left
    }

    #[inline]
    fn set_left(&mut self, left: Option<NonNull<Self>>) {
        self.left = left
    }

    #[inline]
    fn right(&self) -> Option<NonNull<Self>> {
        self.right
    }

    #[inline]
    fn set_right(&mut self, right: Option<NonNull<Self>>) {
        self.right = right
    }

    #[inline]
    fn parent(&self) -> Option<NonNull<Self>> {
        self.parent
    }

    #[inline]
    fn set_parent(&mut self, parent: Option<NonNull<Self>>) {
        self.parent = parent
    }
}

pub struct WeightedBNode<T> {
    weight: i64,
    value: T,
    parent: Option<NonNull<WeightedBNode<T>>>,
    left: Option<NonNull<WeightedBNode<T>>>,
    right: Option<NonNull<WeightedBNode<T>>>,
}

impl<T: Clone> BNodeBase<T> for WeightedBNode<T> {
    #[inline]
    fn create(val: T) -> Box<Self> {
        Box::new(WeightedBNode {
            weight: 0,
            value: val,
            parent: None,
            left: None,
            right: None,
        })
    }

    #[inline]
    fn value(&self) -> T {
        self.value.clone()
    }

    #[inline]
    fn set_value(&mut self, val: T) {
        unsafe { write(&mut self.value, val) }
    }

    #[inline]
    fn left(&self) -> Option<NonNull<Self>> {
        self.left
    }

    #[inline]
    fn set_left(&mut self, left: Option<NonNull<Self>>) {
        self.left = left
    }

    #[inline]
    fn right(&self) -> Option<NonNull<Self>> {
        self.right
    }

    #[inline]
    fn set_right(&mut self, right: Option<NonNull<Self>>) {
        self.right = right
    }

    #[inline]
    fn parent(&self) -> Option<NonNull<Self>> {
        self.parent
    }

    #[inline]
    fn set_parent(&mut self, parent: Option<NonNull<Self>>) {
        self.parent = parent
    }
}

impl<T: Clone> WeightedBNodeBase<T> for WeightedBNode<T> {
    #[inline]
    fn weight(&self) -> i64 {
        self.weight
    }

    #[inline]
    fn set_weight(&mut self, weight: i64) {
        self.weight = weight
    }
}

struct RedBlackNode<K, V> {
    key: K,
    value: V,
    color: Color,
    parent: Option<NonNull<RedBlackNode<K, V>>>,
    left: Option<NonNull<RedBlackNode<K, V>>>,
    right: Option<NonNull<RedBlackNode<K, V>>>,
}

impl<K, V> BNodeBase<V> for RedBlackNode<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn create(val: V) -> Box<Self> {
        Box::new(Self {
            key: Default::default(),
            value: val,
            color: Color::Red,
            parent: None,
            left: None,
            right: None,
        })
    }

    #[inline]
    fn value(&self) -> V {
        self.value.clone()
    }

    #[inline]
    fn set_value(&mut self, val: V) {
        unsafe { write(&mut self.value, val) }
    }

    #[inline]
    fn left(&self) -> Option<NonNull<Self>> {
        self.left
    }

    #[inline]
    fn set_left(&mut self, left: Option<NonNull<Self>>) {
        self.left = left
    }

    #[inline]
    fn right(&self) -> Option<NonNull<Self>> {
        self.right
    }

    #[inline]
    fn set_right(&mut self, right: Option<NonNull<Self>>) {
        self.right = right
    }

    #[inline]
    fn parent(&self) -> Option<NonNull<Self>> {
        self.parent
    }

    #[inline]
    fn set_parent(&mut self, parent: Option<NonNull<Self>>) {
        self.parent = parent
    }
}

impl<K, V> BinarySearchNodeBase<K, V> for RedBlackNode<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn set_key(&mut self, key: K) {
        self.key = key
    }

    #[inline]
    fn key(&self) -> K {
        self.key
    }
}

impl<K, V> RedBlackNodeBase<K, V> for RedBlackNode<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn color(&self) -> Color {
        self.color
    }

    fn examine_after_insert(&mut self) {
        unsafe {
            if let Some(par) = self.parent {
                let mut parent = par.as_ptr();
                if (*parent).color == Color::Red {
                    let grandpa = (*parent).parent.unwrap().as_ptr();
                    match self.uncle() {
                        Some(unc) if (*unc.as_ptr()).color == Color::Red => {
                            // uncle exists and be colored as red
                            (*parent).repigment();
                            (*unc.as_ptr()).repigment();
                            (*grandpa).repigment();
                            (*grandpa).examine_after_insert();
                        }
                        _ => {
                            let mut node: NonNull<Self> = self.into();
                            // uncle does not exist or be colored as black, and
                            // the hand of pivot in parent is opposite to the hand of parent in root
                            if (*parent).right == Some(node) && (*grandpa).left == Some(par) {
                                self.rotate_left();
                                parent = node.as_ptr();
                                node = self.left.unwrap();
                            } else if (*parent).left == Some(node) && (*grandpa).right == Some(par)
                            {
                                self.rotate_right();
                                parent = node.as_ptr();
                                node = self.right.unwrap();
                            }
                            // uncle does not exist or be colored as black, and
                            // the hand of pivot in parent is the same as the hand of parent in root
                            (*parent).repigment();
                            (*grandpa).repigment();
                            if (*parent).left == Some(node) && (*grandpa).left == Some(par) {
                                (*parent).rotate_right();
                            } else {
                                (*parent).rotate_left();
                            }
                        }
                    }
                }
            // else tree is valid
            } else {
                // no parent node
                self.repigment();
            }
        }
    }

    fn examine_after_delete(&mut self) {
        // suppose that the color of the node and deleted node is black
        unsafe {
            if let Some(parent) = self.parent {
                let is_left = (*parent.as_ptr()).left == Some(self.into());
                let sibling = self.sibling().unwrap();
                // sibling is red
                if (*sibling.as_ptr()).color == Color::Red {
                    (*parent.as_ptr()).repigment();
                    (*sibling.as_ptr()).repigment();
                    match is_left {
                        true => (*parent.as_ptr()).rotate_left(),
                        false => (*parent.as_ptr()).rotate_right(),
                    }
                }
                let sibling = self.sibling().unwrap();
                let (color_sl, color_sr) =
                    match ((*sibling.as_ptr()).left, (*sibling.as_ptr()).right) {
                        (None, None) => (Color::Black, Color::Black),
                        (Some(x), None) => ((*x.as_ptr()).color, Color::Black),
                        (None, Some(x)) => (Color::Black, (*x.as_ptr()).color),
                        (Some(x), Some(y)) => ((*x.as_ptr()).color, (*y.as_ptr()).color),
                    };
                // new sbling and its children are black
                if (*sibling.as_ptr()).color == Color::Black
                    && color_sl == Color::Black
                    && color_sr == Color::Black
                {
                    match (*parent.as_ptr()).color {
                        // parent is blak
                        Color::Black => {
                            (*sibling.as_ptr()).repigment();
                            (*parent.as_ptr()).examine_after_delete();
                        }
                        // parent is red
                        Color::Red => {
                            (*sibling.as_ptr()).repigment();
                            (*parent.as_ptr()).repigment();
                        }
                    }
                } else {
                    // if (*sibling.as_ptr()).color == Color::Black
                    if is_left && color_sr == Color::Black {
                        // && color_sl == Color::Red
                        (*sibling.as_ptr()).repigment();
                        let left = (*sibling.as_ptr()).left.unwrap();
                        (*left.as_ptr()).repigment();
                        (*sibling.as_ptr()).rotate_right();
                    } else if !is_left && color_sl == Color::Black {
                        // && color_sr == Color::Red
                        (*sibling.as_ptr()).repigment();
                        let right = (*sibling.as_ptr()).right.unwrap();
                        (*right.as_ptr()).repigment();
                        (*sibling.as_ptr()).rotate_left();
                    }
                    let sibling = self.sibling().unwrap();
                    (*sibling.as_ptr()).color = (*parent.as_ptr()).color;
                    (*parent.as_ptr()).color = Color::Black;
                    if is_left {
                        // sibling's right is red
                        let right = (*sibling.as_ptr()).right.unwrap();
                        (*right.as_ptr()).repigment();
                        (*parent.as_ptr()).rotate_left();
                    } else {
                        // sibling's left is red
                        let left = (*sibling.as_ptr()).left.unwrap();
                        (*left.as_ptr()).repigment();
                        (*parent.as_ptr()).rotate_right();
                    }
                }
            }
            // else parent is None
        }
    }

    #[inline]
    fn repigment(&mut self) {
        self.color = -self.color
    }
}

struct ThreadedAVLNode<K, V> {
    key: K,
    value: V,
    parent: Option<NonNull<ThreadedAVLNode<K, V>>>,
    left: Option<NonNull<ThreadedAVLNode<K, V>>>,
    left_tag: ThreadField,
    right: Option<NonNull<ThreadedAVLNode<K, V>>>,
    right_tag: ThreadField,
    balance: AVLFactor,
}

impl<K, V> BNodeBase<V> for ThreadedAVLNode<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn create(val: V) -> Box<Self> {
        Box::new(Self {
            key: Default::default(),
            value: val,
            parent: None,
            left: None,
            left_tag: ThreadField::Thread,
            right: None,
            right_tag: ThreadField::Thread,
            balance: AVLFactor::Zero,
        })
    }

    #[inline]
    fn value(&self) -> V {
        self.value.clone()
    }

    #[inline]
    fn set_value(&mut self, val: V) {
        unsafe { write(&mut self.value, val) }
    }

    #[inline]
    fn left(&self) -> Option<NonNull<Self>> {
        self.left
    }

    #[inline]
    fn set_left(&mut self, left: Option<NonNull<Self>>) {
        self.left = left
    }

    #[inline]
    fn right(&self) -> Option<NonNull<Self>> {
        self.right
    }

    #[inline]
    fn set_right(&mut self, right: Option<NonNull<Self>>) {
        self.right = right
    }

    #[inline]
    fn parent(&self) -> Option<NonNull<Self>> {
        self.parent
    }

    #[inline]
    fn set_parent(&mut self, parent: Option<NonNull<Self>>) {
        self.parent = parent
    }
}

impl<K, V> BinarySearchNodeBase<K, V> for ThreadedAVLNode<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn set_key(&mut self, key: K) {
        self.key = key
    }

    #[inline]
    fn key(&self) -> K {
        self.key
    }
}

impl<K, V> ThreadedAVLNodeBase<K, V> for ThreadedAVLNode<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn balance_factor(&self) -> AVLFactor {
        self.balance
    }

    #[inline]
    fn update_factor(&mut self, factor: AVLFactor) {
        self.balance = factor;
    }

    #[inline]
    fn left_field(&self) -> ThreadField {
        self.left_tag
    }

    #[inline]
    fn right_field(&self) -> ThreadField {
        self.right_tag
    }

    #[inline]
    fn set_left_with_field(&mut self, left: Option<NonNull<Self>>, field: ThreadField) {
        self.left = left;
        self.left_tag = field;
    }

    #[inline]
    fn set_right_with_field(&mut self, right: Option<NonNull<Self>>, field: ThreadField) {
        self.right = right;
        self.right_tag = field;
    }
}

#[derive(Copy, Clone)]
struct IterPointer<N>(u64, NonNull<N>);

#[derive(Clone)]
struct PreIter<'a, N: 'a> {
    size: u64,
    nodes: Vec<IterPointer<N>>,
    marker: PhantomData<&'a N>,
}

impl<N> PreIter<'_, N> {
    pub fn create(length: u64, root: Option<NonNull<N>>) -> Self {
        let depth = (length + 1).next_power_of_two().trailing_zeros() as usize + 1;
        let mut stack = Vec::<IterPointer<N>>::with_capacity(depth);
        if let Some(r) = root {
            stack.push(IterPointer(1, r));
            PreIter {
                size: length,
                nodes: stack,
                marker: PhantomData,
            }
        } else {
            PreIter {
                size: 0,
                nodes: stack,
                marker: PhantomData,
            }
        }
    }
}

#[derive(Clone)]
struct MidIter<'a, N: 'a> {
    size: u64,
    last_pos: u64,
    nodes: Vec<IterPointer<N>>,
    marker: PhantomData<&'a N>,
}

impl<N> MidIter<'_, N> {
    pub fn create(length: u64, root: Option<NonNull<N>>) -> Self {
        let depth = (length + 1).next_power_of_two().trailing_zeros() as usize + 1;
        let mut stack = Vec::<IterPointer<N>>::with_capacity(depth * 2 - 1);
        if let Some(r) = root {
            stack.push(IterPointer(1, r));
            MidIter {
                size: length,
                last_pos: 0,
                nodes: stack,
                marker: PhantomData,
            }
        } else {
            MidIter {
                size: 0,
                last_pos: 0,
                nodes: stack,
                marker: PhantomData,
            }
        }
    }
}

#[derive(Clone)]
struct PostIter<'a, N: 'a> {
    size: u64,
    last_pos: u64,
    nodes: Vec<IterPointer<N>>,
    marker: PhantomData<&'a N>,
}

impl<N> PostIter<'_, N> {
    pub fn create(length: u64, root: Option<NonNull<N>>) -> Self {
        let depth = (length + 1).next_power_of_two().trailing_zeros() as usize + 1;
        let mut stack = Vec::<IterPointer<N>>::with_capacity(depth * 2 - 1);
        if let Some(r) = root {
            stack.push(IterPointer(1, r));
            PostIter {
                size: length,
                last_pos: 0,
                nodes: stack,
                marker: PhantomData,
            }
        } else {
            PostIter {
                size: 0,
                last_pos: 0,
                nodes: stack,
                marker: PhantomData,
            }
        }
    }
}

#[derive(Clone)]
struct BfsIter<'a, N: 'a> {
    size: u64,
    pos: usize,
    only_leaves: bool,
    nodes: Vec<IterPointer<N>>,
    marker: PhantomData<&'a N>,
}

impl<N> BfsIter<'_, N> {
    pub fn create(length: u64, root: Option<NonNull<N>>, leaves: bool) -> Self {
        let mut queue = Vec::<IterPointer<N>>::with_capacity(length as usize);
        if let Some(r) = root {
            queue.push(IterPointer(1, r));
            BfsIter {
                size: length,
                pos: 0,
                only_leaves: leaves,
                nodes: queue,
                marker: PhantomData,
            }
        } else {
            BfsIter {
                size: 0,
                pos: 0,
                only_leaves: leaves,
                nodes: queue,
                marker: PhantomData,
            }
        }
    }
}

impl<N, T> TreeIterator<N, T> for PreIter<'_, N>
where
    T: Sized + Clone,
    N: BNodeBase<T>,
{
    #[inline]
    fn enumerate(&mut self) -> (u64, Option<NonNull<N>>) {
        unsafe {
            while let Some(IterPointer(idx, node)) = self.nodes.pop() {
                if let Some(x) = (*node.as_ptr()).right() {
                    self.nodes.push(IterPointer(idx * 2 + 1, x));
                }
                if let Some(x) = (*node.as_ptr()).left() {
                    self.nodes.push(IterPointer(idx * 2, x));
                }
                return (idx - 1, Some(node));
            }
        }
        (0, None)
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }
}

impl<N, T> TreeIterator<N, T> for MidIter<'_, N>
where
    T: Sized + Clone,
    N: BNodeBase<T>,
{
    #[inline]
    fn enumerate(&mut self) -> (u64, Option<NonNull<N>>) {
        unsafe {
            while let Some(IterPointer(idx, node)) = self.nodes.pop() {
                if (*node.as_ptr()).is_leaf() || self.last_pos > idx {
                    self.last_pos = idx;
                    return (idx - 1, Some(node));
                } else {
                    if let Some(x) = (*node.as_ptr()).right() {
                        self.nodes.push(IterPointer(idx * 2 + 1, x));
                    }
                    self.nodes.push(IterPointer(idx, node));
                    if let Some(x) = (*node.as_ptr()).left() {
                        self.nodes.push(IterPointer(idx * 2, x));
                    } else {
                        self.last_pos = idx * 2;
                    }
                }
            }
        }
        (0, None)
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }
}

impl<N, T> TreeIterator<N, T> for PostIter<'_, N>
where
    T: Sized + Clone,
    N: BNodeBase<T>,
{
    #[inline]
    fn enumerate(&mut self) -> (u64, Option<NonNull<N>>) {
        while self.nodes.len() > 0 {
            unsafe {
                let IterPointer(idx, node) = self.nodes[self.nodes.len() - 1];
                if (*node.as_ptr()).is_leaf() || self.last_pos > idx {
                    self.nodes.pop();
                    self.last_pos = idx;
                    return (idx - 1, Some(node));
                } else {
                    if let Some(x) = (*node.as_ptr()).right() {
                        self.nodes.push(IterPointer(idx * 2 + 1, x));
                    }
                    if let Some(x) = (*node.as_ptr()).left() {
                        self.nodes.push(IterPointer(idx * 2, x));
                    } else {
                        self.last_pos = idx * 2;
                    }
                }
            }
        }
        (0, None)
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }
}

impl<N, T> TreeIterator<N, T> for BfsIter<'_, N>
where
    T: Sized + Clone,
    N: BNodeBase<T>,
{
    #[inline]
    fn enumerate(&mut self) -> (u64, Option<NonNull<N>>) {
        while self.pos < self.nodes.len() {
            let IterPointer(idx, node) = self.nodes[self.pos];
            unsafe {
                if let Some(x) = (*node.as_ptr()).left() {
                    self.nodes.push(IterPointer(idx * 2, x));
                }
                if let Some(x) = (*node.as_ptr()).right() {
                    self.nodes.push(IterPointer(idx * 2 + 1, x));
                }
                if !self.only_leaves || (*node.as_ptr()).is_leaf() {
                    return (idx - 1, Some(node));
                }
            }
            self.pos += 1;
        }
        (0, None)
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }
}

#[derive(Clone, Default)]
pub struct CompleteBTree<N> {
    size: u64,
    leaves: u64,
    root: Option<NonNull<N>>,
    marker: PhantomData<Box<N>>,
}

impl<N> CompleteBTree<N> {
    #[inline]
    fn index<T>(&mut self, x: u64) -> Option<NonNull<N>>
    where
        T: Clone + Sized,
        N: BNodeBase<T>,
    {
        if x >= self.size {
            None
        } else {
            unsafe {
                let idx = x + 1;
                let mut node = self.root;
                let mut choicer = (idx + 1u64).next_power_of_two() / 4;
                while choicer > 0 {
                    node = match (idx / choicer) % 2 == 0 {
                        true => (*node.unwrap().as_ptr()).left(),
                        false => (*node.unwrap().as_ptr()).right(),
                    };
                    choicer /= 2;
                }
                node
            }
        }
    }
}

impl<N, T> BTreeBase<T> for CompleteBTree<N>
where
    T: Clone + Sized + Ord,
    N: BNodeBase<T>,
{
    #[inline]
    fn new() -> Self {
        CompleteBTree {
            size: 0,
            leaves: 0,
            root: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn append(&mut self, val: T) {
        self.size += 1;
        let mut node = N::create(val);
        if let Some(mut parent) = self.root {
            unsafe {
                let mut choicer = (self.size + 1u64).next_power_of_two() / 4;
                while choicer > 1 {
                    parent = match (self.size / choicer) % 2 == 0 {
                        true => (*parent.as_ptr()).left().unwrap(),
                        false => (*parent.as_ptr()).right().unwrap(),
                    };
                    choicer /= 2;
                }
                node.set_parent(Some(parent));
                if self.size % 2 == 0 {
                    (*parent.as_ptr()).set_left(Some(Box::leak(node).into()));
                } else {
                    (*parent.as_ptr()).set_right(Some(Box::leak(node).into()));
                    self.leaves += 1;
                }
            }
        } else {
            self.root = Some(Box::leak(node).into());
            self.leaves = 1;
        }
    }

    #[inline]
    fn delete(&mut self, val: T) {
        let iter = PreIter::create(self.size, self.root);
        if let Some(node) = iter.find(|v| v == val) {
            unsafe {
                let last = Box::from_raw(self.index(self.size - 1).unwrap().as_ptr());
                (*node.as_ptr()).set_value(last.value());
                if self.size % 2 == 1 {
                    self.leaves -= 1;
                }
                self.size -= 1;
            }
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }

    #[inline]
    fn leaves(&self) -> u64 {
        self.leaves
    }

    fn min(&self) -> Option<T> {
        self.root.map(|root| unsafe {
            let iter = PreIter::create(self.size, self.root);
            let init = (*root.as_ptr()).value();
            iter.fold(init, |l, r| l.min(r))
        })
    }

    fn max(&self) -> Option<T> {
        self.root.map(|root| unsafe {
            let iter = PreIter::create(self.size, self.root);
            let init = (*root.as_ptr()).value();
            iter.fold(init, |l, r| l.max(r))
        })
    }

    fn find_by<F: FnMut(T) -> bool>(&self, f: F) -> Vec<T> {
        if !self.root.is_none() {
            let iter = PreIter::create(self.size, self.root);
            let nodes = iter.filter(f);
            nodes
                .into_iter()
                .map(|p| unsafe { (*p.as_ptr()).value() })
                .collect()
        } else {
            Vec::new()
        }
    }

    fn traverse<F, U>(&mut self, f: F, order: TraverseOrd) -> Vec<U>
    where
        F: FnMut(T) -> U,
    {
        if !self.root.is_none() {
            match order {
                TraverseOrd::PreOrd => PreIter::create(self.size, self.root).map(f),
                TraverseOrd::MidOrd => MidIter::create(self.size, self.root).map(f),
                TraverseOrd::PostOrd => PostIter::create(self.size, self.root).map(f),
                TraverseOrd::LevelOrd => BfsIter::create(self.size, self.root, false).map(f),
                TraverseOrd::LeavesOrd => BfsIter::create(self.size, self.root, true).map(f),
            }
        } else {
            Vec::new()
        }
    }
}

#[derive(Clone, Default)]
pub struct OrderedBTree<N> {
    size: u64,
    leaves: u64,
    asc: bool,
    root: Option<NonNull<N>>,
    marker: PhantomData<Box<N>>,
}

impl<N> OrderedBTree<N> {
    #[inline]
    pub fn ascending() -> Self {
        Self {
            size: 0,
            leaves: 0,
            asc: true,
            root: None,
            marker: PhantomData,
        }
    }

    #[inline]
    pub fn descending() -> Self {
        Self {
            size: 0,
            leaves: 0,
            asc: false,
            root: None,
            marker: PhantomData,
        }
    }
}

impl<N, T> BTreeBase<T> for OrderedBTree<N>
where
    T: Clone + Sized + Ord,
    N: BNodeBase<T>,
{
    #[inline]
    fn new() -> Self {
        OrderedBTree {
            size: 0,
            leaves: 0,
            asc: true,
            root: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn append(&mut self, val: T) {
        self.size += 1;
        let mut node = N::create(val.clone());
        if let Some(mut parent) = self.root {
            unsafe {
                loop {
                    let pval = (*parent.as_ptr()).value();
                    let (branch, is_left) =
                        match (self.asc && val <= pval) || (!self.asc && val > pval) {
                            true => ((*parent.as_ptr()).left(), true),
                            false => ((*parent.as_ptr()).right(), false),
                        };
                    if let Some(b) = branch {
                        parent = b;
                    } else {
                        node.set_parent(Some(parent));
                        if !(*parent.as_ptr()).is_leaf() {
                            self.leaves += 1
                        }
                        if is_left {
                            (*parent.as_ptr()).set_left(Some(Box::leak(node).into()));
                        } else {
                            (*parent.as_ptr()).set_right(Some(Box::leak(node).into()));
                        }
                        break;
                    }
                }
            }
        } else {
            self.root = Some(Box::leak(node).into());
            self.leaves = 1;
        }
    }

    #[inline]
    fn delete(&mut self, val: T) {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                let pval = (*ptr.as_ptr()).value();
                if pval == val {
                    break;
                } else if (self.asc && val < pval) || (!self.asc && val > pval) {
                    node = (*ptr.as_ptr()).left();
                } else {
                    node = (*ptr.as_ptr()).right();
                }
            }
            if let Some(mut ptr) = node {
                let (parent, left, right) = (
                    (*ptr.as_ptr()).parent(),
                    (*ptr.as_ptr()).left(),
                    (*ptr.as_ptr()).right(),
                );
                if let Some(lef) = left {
                    let mut max_lef = lef;
                    while let Some(l) = (*max_lef.as_ptr()).right() {
                        max_lef = l;
                    }
                    (*ptr.as_ptr()).set_value((*max_lef.as_ptr()).value());
                    let max_lef_par = (*max_lef.as_ptr()).parent();
                    let max_lef_lef = (*max_lef.as_ptr()).left();
                    if let Some(x) = max_lef_lef {
                        (*x.as_ptr()).set_parent(max_lef_par);
                    }
                    if max_lef_par == node {
                        (*ptr.as_ptr()).set_left(max_lef_lef);
                    } else {
                        (*max_lef_par.unwrap().as_ptr()).set_right(max_lef_lef);
                    }
                    ptr = max_lef;
                } else {
                    if let Some(par) = parent {
                        if let Some(rig) = right {
                            (*rig.as_ptr()).set_parent(parent);
                        }
                        if (*par.as_ptr()).left() == node {
                            (*par.as_ptr()).set_left(right);
                        } else {
                            (*par.as_ptr()).set_right(right);
                        }
                        if !(*par.as_ptr()).is_leaf() {
                            self.leaves -= 1;
                        }
                    } else if let Some(rig) = right {
                        self.root = right;
                        (*rig.as_ptr()).set_parent(None);
                    } else {
                        self.root = None;
                        self.leaves -= 1;
                    }
                }
                let _boxed = Box::from_raw(ptr.as_ptr());
                self.size -= 1;
            }
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new()
    }

    #[inline]
    fn size(&self) -> u64 {
        self.size
    }

    #[inline]
    fn leaves(&self) -> u64 {
        self.leaves
    }

    #[inline]
    fn min(&self) -> Option<T> {
        self.root.map(|root| unsafe {
            let mut minium = root;
            if self.asc {
                while let Some(r) = (*minium.as_ptr()).left() {
                    minium = r;
                }
            } else {
                while let Some(r) = (*minium.as_ptr()).right() {
                    minium = r;
                }
            }
            (*minium.as_ptr()).value()
        })
    }

    #[inline]
    fn max(&self) -> Option<T> {
        self.root.map(|root| unsafe {
            let mut minium = root;
            if self.asc {
                while let Some(r) = (*minium.as_ptr()).right() {
                    minium = r;
                }
            } else {
                while let Some(r) = (*minium.as_ptr()).left() {
                    minium = r;
                }
            }
            (*minium.as_ptr()).value()
        })
    }

    #[inline]
    fn find_by<F: FnMut(T) -> bool>(&self, f: F) -> Vec<T> {
        if !self.root.is_none() {
            let iter = MidIter::create(self.size, self.root);
            let nodes = iter.filter(f);
            nodes
                .into_iter()
                .map(|p| unsafe { (*p.as_ptr()).value() })
                .collect()
        } else {
            Vec::new()
        }
    }

    #[inline]
    fn traverse<F, U>(&mut self, f: F, order: TraverseOrd) -> Vec<U>
    where
        F: FnMut(T) -> U,
    {
        if !self.root.is_none() {
            match order {
                TraverseOrd::PreOrd => PreIter::create(self.size, self.root).map(f),
                TraverseOrd::MidOrd => MidIter::create(self.size, self.root).map(f),
                TraverseOrd::PostOrd => PostIter::create(self.size, self.root).map(f),
                TraverseOrd::LevelOrd => BfsIter::create(self.size, self.root, false).map(f),
                TraverseOrd::LeavesOrd => BfsIter::create(self.size, self.root, true).map(f),
            }
        } else {
            Vec::new()
        }
    }
}

#[derive(Copy, Clone)]
pub struct HuffCode(u64, u64);

impl HuffCode {
    #[inline]
    pub fn from_index(idx: u64) -> Self {
        let mask = 1 << (63 - (idx + 1).leading_zeros()) - 1;
        HuffCode((idx + 1) & mask, mask.trailing_ones() as u64)
    }
}

#[derive(Clone)]
pub struct HuffmanTree<N> {
    size: u64,
    leaves: u64,
    root: Option<NonNull<N>>,
    marker: PhantomData<Box<N>>,
}

impl<N> HuffmanTree<N> {
    #[inline]
    fn to_table<T>(&self) -> HashMap<T, HuffCode>
    where
        T: Clone + Sized + Hash + Eq,
        N: WeightedBNodeBase<Option<T>>,
    {
        let mut iter = BfsIter::create(self.size, self.root, true);
        let mut map = HashMap::<T, HuffCode>::with_capacity(self.leaves as usize);
        while let (idx, Some(val)) = iter.enumerate() {
            unsafe {
                map.insert((*val.as_ptr()).value().unwrap(), HuffCode::from_index(idx));
            }
        }
        map
    }
}

impl<N> HuffmanTree<N> {
    #[inline]
    pub fn create<T>(vals: HashMap<T, i64>) -> Self
    where
        T: Clone + Sized + Hash + Eq,
        N: WeightedBNodeBase<Option<T>>,
    {
        unsafe {
            let len = vals.len() as u64;
            let mut nodes: Vec<NonNull<N>> = vals
                .into_iter()
                .map(|params| {
                    let (value, weight) = params;
                    let mut node = N::create(Some(value));
                    node.set_weight(weight);
                    Box::leak(node).into()
                })
                .collect::<Vec<_>>();
            while nodes.len() > 2 {
                let (l, w_l, r, w_r) =
                    nodes
                        .iter()
                        .enumerate()
                        .fold((0, i64::MIN, 0, i64::MIN), |accum, x| {
                            let (idx, node) = x;
                            let (l, w_l, _, w_r) = accum;
                            match (*node.as_ptr()).weight() {
                                weight if weight < w_l => (idx, weight, l, w_l),
                                weight if weight < w_r => (l, w_l, idx, weight),
                                _ => accum,
                            }
                        });
                let (mut parent, left, right) = (N::create(None), nodes[l], nodes[r]);
                parent.set_left(Some(left));
                parent.set_right(Some(right));
                parent.set_weight(w_l + w_r);
                let parent: NonNull<N> = Box::leak(parent).into();
                (*left.as_ptr()).set_parent(Some(parent));
                (*right.as_ptr()).set_parent(Some(parent));
                nodes[l] = parent;
                nodes[r] = nodes[nodes.len() - 1];
                nodes.pop();
            }
            let (n_0, n_1) = (nodes[0], nodes[1]);
            let (w_0, w_1) = ((*n_0.as_ptr()).weight(), (*n_1.as_ptr()).weight());
            let mut parent = N::create(None);
            parent.set_weight(w_0 + w_1);
            if w_0 < w_1 {
                parent.set_left(Some(n_0));
                parent.set_right(Some(n_1));
            } else {
                parent.set_left(Some(n_1));
                parent.set_right(Some(n_0));
            }
            let parent: NonNull<N> = Box::leak(parent).into();
            (*n_0.as_ptr()).set_parent(Some(parent));
            (*n_1.as_ptr()).set_parent(Some(parent));

            Self {
                size: len * 2 - 1,
                leaves: len,
                root: Some(parent),
                marker: PhantomData,
            }
        }
    }

    #[inline]
    pub fn into_table<T>(self) -> HashMap<T, HuffCode>
    where
        T: Clone + Sized + Hash + Eq,
        N: WeightedBNodeBase<Option<T>>,
    {
        self.to_table()
    }

    #[inline]
    pub fn encode<T>(&self, raw: Vec<T>) -> Vec<u64>
    where
        T: Clone + Sized + Hash + Eq + Debug,
        N: WeightedBNodeBase<Option<T>>,
    {
        let table: HashMap<T, HuffCode> = self.to_table();
        let mut data = Vec::<u64>::with_capacity(raw.len());
        let (mut buffer, mut bits) = (0u64, 64u64);
        for it in raw.iter() {
            if let Some(&HuffCode(code, bitlen)) = table.get(it) {
                if bits >= bitlen {
                    bits -= bitlen;
                    buffer |= code << bits;
                } else {
                    buffer |= code >> (bitlen - bits);
                    data.push(buffer);
                    bits = 64 + bits - bitlen;
                    buffer = code << bits;
                }
            } else {
                panic!("unexpected token: {:?}", it);
            }
        }
        data.shrink_to_fit();
        data
    }

    #[inline]
    pub fn decode<T>(&self, data: Vec<u64>, mut len: usize) -> Vec<T>
    where
        T: Clone + Sized + Hash + Eq,
        N: WeightedBNodeBase<Option<T>>,
    {
        let (mut node, mut mask) = (self.root.unwrap(), 1u64 << 63);
        let mut raw = Vec::<T>::with_capacity(len);
        unsafe {
            for it in data.into_iter() {
                while mask > 0 && len > 0 {
                    node = match it & mask == 0 {
                        true => (*node.as_ptr()).left().unwrap(),
                        false => (*node.as_ptr()).right().unwrap(),
                    };
                    if (*node.as_ptr()).is_leaf() {
                        len -= 1;
                        raw.push((*node.as_ptr()).value().unwrap());
                        node = self.root.unwrap();
                    }
                    mask >>= 1;
                }
                mask = 1u64 << 63;
            }
        }
        raw.shrink_to_fit();
        raw
    }

    #[inline]
    pub fn size(&self) -> u64 {
        self.leaves
    }
}

#[derive(Clone)]
pub struct SegmentTree {
    low: i64,
    high: i64,
    root: Option<NonNull<BNode<u64>>>,
    marker: PhantomData<Box<BNode<u64>>>,
}

impl SegmentTree {
    fn create_node(inf: i64, sup: i64) -> Box<BNode<u64>> {
        let mut node = BNode::create(0u64);
        if (sup - inf) > 1 {
            let mid = (sup + inf) / 2;
            node.set_left(Some(Box::leak(Self::create_node(inf, mid)).into()));
            node.set_left(Some(Box::leak(Self::create_node(mid, sup)).into()));
        }
        node
    }

    fn node_counts(node: NonNull<BNode<u64>>, lo: i64, hi: i64, inf: i64, sup: i64, counts: u64) {
        unsafe {
            if lo >= inf && hi <= sup {
                let val = (*node.as_ptr()).value();
                (*node.as_ptr()).set_value(val + counts);
            } else {
                if let Some(x) = (*node.as_ptr()).left() {
                    Self::node_counts(x, lo, (lo + hi) / 2, inf, sup, counts);
                }
                if let Some(x) = (*node.as_ptr()).right() {
                    Self::node_counts(x, (lo + hi) / 2, hi, inf, sup, counts);
                }
            }
        }
    }

    fn node_accum<F>(node: NonNull<BNode<u64>>, lo: i64, hi: i64, inf: i64, sup: i64, f: F) -> u64
    where
        F: FnOnce(u64, u64) -> u64 + Copy,
    {
        unsafe {
            let node = node.as_ptr();
            if lo >= sup || hi <= inf {
                0
            } else if (*node).is_leaf() {
                (*node).value()
            } else {
                (*node).value()
                    + f(
                        Self::node_accum((*node).left().unwrap(), lo, (lo + hi) / 2, inf, sup, f),
                        Self::node_accum((*node).right().unwrap(), (lo + hi) / 2, hi, inf, sup, f),
                    )
            }
        }
    }
}

impl SegmentTree {
    #[inline]
    pub fn create(inf: i64, sup: i64) -> Self {
        assert!(sup > inf, "lower bound is higher than upper bound.");
        let node = SegmentTree::create_node(inf, sup);
        Self {
            low: inf,
            high: sup,
            root: Some(Box::leak(node).into()),
            marker: PhantomData,
        }
    }

    #[inline]
    pub fn counts(&mut self, inf: i64, sup: i64, counts: u64) {
        assert!(sup > inf, "lower bound is higher than upper bound.");
        if let Some(root) = self.root {
            Self::node_counts(root, self.low, self.high, inf, sup, counts);
        }
    }

    #[inline]
    pub fn count(&mut self, inf: i64, sup: i64) {
        assert!(sup > inf, "lower bound is higher than upper bound.");
        if let Some(root) = self.root {
            Self::node_counts(root, self.low, self.high, inf, sup, 1);
        }
    }

    #[inline]
    pub fn min(&self, inf: i64, sup: i64) -> u64 {
        assert!(sup > inf, "lower bound is higher than upper bound.");
        if let Some(root) = self.root {
            return Self::node_accum(root, self.low, self.high, inf, sup, min::<u64>);
        }
        0
    }

    #[inline]
    pub fn max(&self, inf: i64, sup: i64) -> u64 {
        assert!(sup > inf, "lower bound is higher than upper bound.");
        if let Some(root) = self.root {
            return Self::node_accum(root, self.low, self.high, inf, sup, max::<u64>);
        }
        0
    }
}

#[derive(Clone, Default)]
pub struct RedBlackTree<K, V> {
    size: u64,
    root: Option<NonNull<RedBlackNode<K, V>>>,
    marker: PhantomData<Box<RedBlackNode<K, V>>>,
}

impl<K, V> SearchTreeBase<K, V> for RedBlackTree<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn new() -> Self {
        Self {
            size: 0,
            root: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn insert(&mut self, key: K, val: V) -> bool {
        let node: NonNull<RedBlackNode<K, V>> = Box::leak(RedBlackNode::<K, V>::create(val)).into();
        unsafe {
            (*node.as_ptr()).set_key(key);
            if let Some(mut parent) = self.root {
                while let Some(child) = match (*node.as_ptr()).cmp(parent.as_ref()) {
                    Ordering::Less => (*parent.as_ptr()).left(),
                    Ordering::Greater => (*parent.as_ptr()).right(),
                    Ordering::Equal => return false,
                } {
                    parent = child
                }

                match (*node.as_ptr()).cmp(parent.as_ref()) {
                    Ordering::Less => (*parent.as_ptr()).set_left(Some(node)),
                    Ordering::Greater => (*parent.as_ptr()).set_right(Some(node)),
                    Ordering::Equal => return false,
                };
                (*node.as_ptr()).set_parent(Some(parent));
            } else {
                self.root = Some(node);
            }
            self.size += 1;
            (*node.as_ptr()).examine_after_insert();
            // examine root
            while let Some(root) = self.root {
                match (*root.as_ptr()).parent() {
                    Some(par) => self.root = Some(par),
                    None => break,
                }
            }
            return true;
        }
    }

    #[inline]
    fn delete(&mut self, key: K) -> bool {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                match (*ptr.as_ptr()).cmp_with_key(&key) {
                    Ordering::Less => node = (*ptr.as_ptr()).left(),
                    Ordering::Greater => node = (*ptr.as_ptr()).right(),
                    Ordering::Equal => break,
                }
            }
            if let Some(n) = node {
                let mut pnode = n.as_ptr();
                if !(*pnode).right().is_none() {
                    if let Some(left) = (*pnode).left() {
                        let mut rmost = left.as_ptr();
                        while let Some(rhd) = (*rmost).right() {
                            rmost = rhd.as_ptr();
                        }
                        (*pnode).set_key((*rmost).key());
                        (*pnode).set_value((*rmost).value());
                        pnode = rmost;
                    }
                }
                let mut boxed = Box::from_raw(pnode);
                if boxed.parent().is_none() {
                    self.root = match boxed.right().is_none() {
                        true => boxed.left(),
                        false => boxed.right(),
                    };
                    if let Some(root) = self.root {
                        (*root.as_ptr()).set_parent(None);
                        if (*root.as_ptr()).color() == Color::Red {
                            (*root.as_ptr()).repigment();
                        }
                    }
                } else {
                    boxed.delete_and_examine();
                }

                // examine root
                while let Some(root) = self.root {
                    match (*root.as_ptr()).parent() {
                        Some(par) => self.root = Some(par),
                        None => break,
                    }
                }
                self.size -= 1;
                return true;
            }
            return false;
        }
    }

    #[inline]
    fn update(&mut self, key: K, val: V) {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                match (*ptr.as_ptr()).cmp_with_key(&key) {
                    Ordering::Less => node = (*ptr.as_ptr()).left(),
                    Ordering::Greater => node = (*ptr.as_ptr()).right(),
                    Ordering::Equal => break,
                }
            }
            if let Some(pnode) = node {
                (*pnode.as_ptr()).set_value(val);
            }
        }
    }

    #[inline]
    fn query(&self, key: K) -> Option<V> {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                match (*ptr.as_ptr()).cmp_with_key(&key) {
                    Ordering::Less => node = (*ptr.as_ptr()).left(),
                    Ordering::Greater => node = (*ptr.as_ptr()).right(),
                    Ordering::Equal => break,
                }
            }
            node.map(|node| (*node.as_ptr()).value())
        }
    }

    #[inline]
    fn where_val<F: FnMut(&V) -> bool>(&self, mut f: F) -> Vec<V> {
        unsafe {
            let mut res = Vec::<V>::with_capacity(self.size as usize);
            let mut filter = |_k: K, v: V| match f(&v) {
                true => Some(v),
                false => None,
            };
            if let Some(root) = self.root {
                (*root.as_ptr()).in_order_traverse(&mut res, &mut filter);
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn where_key<F: FnMut(&K) -> bool>(&self, mut f: F) -> Vec<K> {
        unsafe {
            let mut res = Vec::<K>::with_capacity(self.size as usize);
            let mut filter = |k: K, _v: V| match f(&k) {
                true => Some(k),
                false => None,
            };
            if let Some(root) = self.root {
                (*root.as_ptr()).in_order_traverse(&mut res, &mut filter);
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<(K, V)> {
        unsafe {
            let mut res = Vec::<(K, V)>::with_capacity(self.size as usize);
            let mut filter = |k: K, v: V| Some((k, v));
            if let Some(root) = self.root {
                (*root.as_ptr()).in_order_traverse(&mut res, &mut filter);
            }
            res
        }
    }

    #[inline]
    fn min_key(&self) -> Option<K> {
        self.root.map(|mut node| unsafe {
            while let Some(n) = (*node.as_ptr()).left() {
                node = n;
            }
            (*node.as_ptr()).key()
        })
    }

    #[inline]
    fn min_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        self.root.map(|root| unsafe {
            let mut iter = PreIter::create(self.size, self.root);
            let mut min_val = (*root.as_ptr()).value();
            let mut key = (*root.as_ptr()).key();
            while let Some(node) = iter.next() {
                let val = (*node.as_ptr()).value();
                if min_val > val {
                    min_val = val;
                    key = (*node.as_ptr()).key();
                }
            }
            key
        })
    }

    #[inline]
    fn max_key(&self) -> Option<K> {
        self.root.map(|mut node| unsafe {
            while let Some(n) = (*node.as_ptr()).right() {
                node = n;
            }
            (*node.as_ptr()).key()
        })
    }

    #[inline]
    fn max_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        self.root.map(|root| unsafe {
            let mut iter = PreIter::create(self.size, self.root);
            let mut max_val = (*root.as_ptr()).value();
            let mut key = (*root.as_ptr()).key();
            while let Some(node) = iter.next() {
                let val = (*node.as_ptr()).value();
                if max_val < val {
                    max_val = val;
                    key = (*node.as_ptr()).key();
                }
            }
            key
        })
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]
    fn size(&self) -> usize {
        self.size as usize
    }
}

#[derive(Clone, Default)]
pub struct ThreadedAVLTree<K, V> {
    size: u64,
    root: Option<NonNull<ThreadedAVLNode<K, V>>>,
    head: Option<NonNull<ThreadedAVLNode<K, V>>>,
    tail: Option<NonNull<ThreadedAVLNode<K, V>>>,
    marker: PhantomData<Box<ThreadedAVLNode<K, V>>>,
}

impl<K, V> ThreadedAVLTree<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    pub fn recursive_insert(&mut self, key: K, val: V) {
        self.size += 1;
        let node: NonNull<ThreadedAVLNode<K, V>> =
            Box::leak(ThreadedAVLNode::<K, V>::create(val)).into();
        unsafe {
            (*node.as_ptr()).set_key(key);
            if let Some(root) = self.root {
                self.node_recursive(root, node);
            } else {
                self.root = Some(node);
                self.head = Some(node);
                self.tail = Some(node);
            }
            self.examine_root();
        }
    }

    unsafe fn examine_root(&mut self) {
        // examine root
        while let Some(root) = self.root {
            match (*root.as_ptr()).parent() {
                Some(par) => self.root = Some(par),
                None => break,
            }
        }
    }

    unsafe fn node_recursive(
        &mut self,
        node: NonNull<ThreadedAVLNode<K, V>>,
        other: NonNull<ThreadedAVLNode<K, V>>,
    ) -> bool {
        let (field, operator) = match (*other.as_ptr()).cmp(node.as_ref()) {
            Ordering::Less => ((*node.as_ptr()).left_field(), AVLFactor::Minus),
            Ordering::Greater => ((*node.as_ptr()).right_field(), AVLFactor::Plus),
            Ordering::Equal => panic!("keyword exists already"),
        };
        let child = match (field, operator) {
            (ThreadField::Thread, _) => None,
            (ThreadField::Child, AVLFactor::Minus) => (*node.as_ptr()).left(),
            _ => (*node.as_ptr()).right(),
        };
        if let Some(next) = child {
            if self.node_recursive(next, other) {
                return true;
            } else if operator == AVLFactor::Minus {
                match (*node.as_ptr()).balance_factor() {
                    AVLFactor::Plus => {
                        (*node.as_ptr()).update_factor(AVLFactor::Zero);
                        return true;
                    }
                    AVLFactor::Zero => {
                        (*node.as_ptr()).update_factor(AVLFactor::Minus);
                        return false;
                    }
                    _ => {
                        let child = (*node.as_ptr()).left().unwrap();
                        let factor_child = (*child.as_ptr()).balance_factor();
                        let (fp, fc) = match factor_child == AVLFactor::Minus {
                            // rotate right at child
                            true => {
                                (*child.as_ptr()).thread_rotate_right();
                                (AVLFactor::Zero, AVLFactor::Zero)
                            }
                            false => {
                                let grandson = (*child.as_ptr()).right().unwrap();
                                let factor_gs = (*grandson.as_ptr()).balance_factor();
                                // rotate left and then right at grandson
                                (*grandson.as_ptr()).thread_rotate_left();
                                (*grandson.as_ptr()).thread_rotate_right();
                                (*grandson.as_ptr()).update_factor(AVLFactor::Zero);
                                match factor_gs {
                                    AVLFactor::Minus => (AVLFactor::Plus, AVLFactor::Zero),
                                    AVLFactor::Zero => (AVLFactor::Zero, AVLFactor::Zero),
                                    AVLFactor::Plus => (AVLFactor::Zero, AVLFactor::Minus),
                                    _ => panic!("factor is out of bound"),
                                }
                            }
                        };
                        (*node.as_ptr()).update_factor(fp);
                        (*child.as_ptr()).update_factor(fc);
                        return true;
                    }
                }
            } else {
                match (*node.as_ptr()).balance_factor() {
                    AVLFactor::Minus => {
                        (*node.as_ptr()).update_factor(AVLFactor::Zero);
                        return true;
                    }
                    AVLFactor::Zero => {
                        (*node.as_ptr()).update_factor(AVLFactor::Plus);
                        return false;
                    }
                    _ => {
                        let child = (*node.as_ptr()).left().unwrap();
                        let factor_child = (*child.as_ptr()).balance_factor();
                        let (fp, fc) = match factor_child == AVLFactor::Minus {
                            // rotate left at child
                            true => {
                                (*child.as_ptr()).thread_rotate_left();
                                (AVLFactor::Zero, AVLFactor::Zero)
                            }
                            false => {
                                let grandson = (*child.as_ptr()).left().unwrap();
                                let factor_gs = (*grandson.as_ptr()).balance_factor();
                                // rotate right and then left at grandson
                                (*grandson.as_ptr()).thread_rotate_right();
                                (*grandson.as_ptr()).thread_rotate_left();
                                (*grandson.as_ptr()).update_factor(AVLFactor::Zero);
                                match factor_gs {
                                    AVLFactor::Plus => (AVLFactor::Minus, AVLFactor::Zero),
                                    AVLFactor::Zero => (AVLFactor::Zero, AVLFactor::Zero),
                                    AVLFactor::Minus => (AVLFactor::Zero, AVLFactor::Plus),
                                    _ => panic!("factor is out of bound"),
                                }
                            }
                        };
                        (*node.as_ptr()).update_factor(fp);
                        (*child.as_ptr()).update_factor(fc);
                        return true;
                    }
                }
            }
        } else {
            match operator == AVLFactor::Minus {
                true => {
                    (*other.as_ptr()).set_left((*node.as_ptr()).left());
                    (*other.as_ptr()).set_right(Some(node));
                    if (*other.as_ptr()).left().is_none() {
                        self.head = Some(other);
                    }
                    (*node.as_ptr()).set_left_with_field(Some(other), ThreadField::Child);
                }
                false => {
                    (*other.as_ptr()).set_right((*node.as_ptr()).right());
                    (*other.as_ptr()).set_left(Some(node));
                    if (*other.as_ptr()).right().is_none() {
                        self.tail = Some(other);
                    }
                    (*node.as_ptr()).set_right_with_field(Some(other), ThreadField::Child);
                }
            }
            (*other.as_ptr()).set_parent(Some(node));
            match (*node.as_ptr()).balance_factor() == AVLFactor::Zero {
                true => (*node.as_ptr()).update_factor(operator),
                false => (*node.as_ptr()).update_factor(AVLFactor::Zero),
            }
            return false;
        }
    }
}

impl<K, V> SearchTreeBase<K, V> for ThreadedAVLTree<K, V>
where
    K: Ord + Copy + Default,
    V: Clone + Sized,
{
    #[inline]
    fn new() -> Self {
        Self {
            size: 0,
            root: None,
            head: None,
            tail: None,
            marker: PhantomData,
        }
    }

    #[inline]
    fn insert(&mut self, key: K, val: V) -> bool {
        let node: NonNull<ThreadedAVLNode<K, V>> =
            Box::leak(ThreadedAVLNode::<K, V>::create(val)).into();
        unsafe {
            (*node.as_ptr()).set_key(key);
            if let Some(mut parent) = self.root {
                let mut nearest_tiled = parent;
                while let (Some(child), ThreadField::Child) = match (*node.as_ptr())
                    .cmp(parent.as_ref())
                {
                    Ordering::Less => ((*parent.as_ptr()).left(), (*parent.as_ptr()).left_field()),
                    Ordering::Greater => {
                        ((*parent.as_ptr()).right(), (*parent.as_ptr()).right_field())
                    }
                    Ordering::Equal => return false,
                } {
                    parent = child;
                    if !(*parent.as_ptr()).is_balance() {
                        nearest_tiled = parent;
                    }
                }

                let factor = (*parent.as_ptr()).balance_factor();
                let operator = match (*node.as_ptr()).cmp(parent.as_ref()) {
                    Ordering::Less => {
                        (*node.as_ptr()).set_parent(Some(parent));
                        (*node.as_ptr()).set_left((*parent.as_ptr()).left());
                        (*node.as_ptr()).set_right(Some(parent));
                        if (*node.as_ptr()).left().is_none() {
                            self.head = Some(node);
                        }
                        (*parent.as_ptr()).set_left_with_field(Some(node), ThreadField::Child);
                        AVLFactor::Minus
                    }
                    Ordering::Greater => {
                        (*node.as_ptr()).set_parent(Some(parent));
                        (*node.as_ptr()).set_right((*parent.as_ptr()).right());
                        (*node.as_ptr()).set_left(Some(parent));
                        if (*node.as_ptr()).right().is_none() {
                            self.tail = Some(node);
                        }
                        (*parent.as_ptr()).set_right_with_field(Some(node), ThreadField::Child);
                        AVLFactor::Plus
                    }
                    Ordering::Equal => return false,
                };
                if factor == AVLFactor::Zero {
                    (*parent.as_ptr()).update_factor(operator);
                } else {
                    (*parent.as_ptr()).update_factor(AVLFactor::Zero);
                }

                // traverse back to update the factor
                while let Some(par) = (*parent.as_ptr()).parent() {
                    parent = par;
                    if parent == nearest_tiled {
                        let operator = match (*parent.as_ptr()).greater(node.as_ref()) {
                            true => AVLFactor::Minus,
                            false => AVLFactor::Plus,
                        };
                        if (*parent.as_ptr()).balance_factor() == operator {
                            let child = match operator == AVLFactor::Minus {
                                true => (*parent.as_ptr()).left().unwrap(),
                                false => (*parent.as_ptr()).right().unwrap(),
                            };
                            let factor_child = (*child.as_ptr()).balance_factor();

                            let (fp, fc) = match operator == AVLFactor::Minus {
                                true => match factor_child == AVLFactor::Minus {
                                    // rotate right at child
                                    true => {
                                        (*child.as_ptr()).thread_rotate_right();
                                        (AVLFactor::Zero, AVLFactor::Zero)
                                    }
                                    false => {
                                        let grandson = (*child.as_ptr()).right().unwrap();
                                        let factor_gs = (*grandson.as_ptr()).balance_factor();
                                        // rotate left and then right at grandson
                                        (*grandson.as_ptr()).thread_rotate_left();
                                        (*grandson.as_ptr()).thread_rotate_right();
                                        (*grandson.as_ptr()).update_factor(AVLFactor::Zero);
                                        match factor_gs {
                                            AVLFactor::Minus => (AVLFactor::Plus, AVLFactor::Zero),
                                            AVLFactor::Zero => (AVLFactor::Zero, AVLFactor::Zero),
                                            AVLFactor::Plus => (AVLFactor::Zero, AVLFactor::Minus),
                                            _ => panic!("factor is out of bound"),
                                        }
                                    }
                                },
                                false => match factor_child == AVLFactor::Plus {
                                    // rotate left at child
                                    true => {
                                        (*child.as_ptr()).thread_rotate_left();
                                        (AVLFactor::Zero, AVLFactor::Zero)
                                    }
                                    false => {
                                        let grandson = (*child.as_ptr()).left().unwrap();
                                        let factor_gs = (*grandson.as_ptr()).balance_factor();
                                        // rotate right and then left at grandson
                                        (*grandson.as_ptr()).thread_rotate_right();
                                        (*grandson.as_ptr()).thread_rotate_left();
                                        (*grandson.as_ptr()).update_factor(AVLFactor::Zero);
                                        match factor_gs {
                                            AVLFactor::Plus => (AVLFactor::Minus, AVLFactor::Zero),
                                            AVLFactor::Zero => (AVLFactor::Zero, AVLFactor::Zero),
                                            AVLFactor::Minus => (AVLFactor::Zero, AVLFactor::Plus),
                                            _ => panic!("factor is out of bound"),
                                        }
                                    }
                                },
                            };
                            (*parent.as_ptr()).update_factor(fp);
                            (*child.as_ptr()).update_factor(fc);
                        } else {
                            (*parent.as_ptr()).update_factor(operator);
                        }
                        break;
                    } else {
                        match (*parent.as_ptr()).greater(node.as_ref()) {
                            true => (*parent.as_ptr()).update_factor(AVLFactor::Minus),
                            false => (*parent.as_ptr()).update_factor(AVLFactor::Plus),
                        }
                    }
                }
            } else {
                self.root = Some(node);
                self.head = Some(node);
                self.tail = Some(node);
            }
            self.examine_root();
            self.size += 1;
            return true;
        }
    }

    #[inline]
    fn delete(&mut self, key: K) -> bool {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                match (*ptr.as_ptr()).cmp_with_key(&key) {
                    Ordering::Less => {
                        node = match (*ptr.as_ptr()).left_field() {
                            ThreadField::Child => (*ptr.as_ptr()).left(),
                            ThreadField::Thread => None,
                        }
                    }
                    Ordering::Greater => {
                        node = match (*ptr.as_ptr()).right_field() {
                            ThreadField::Child => (*ptr.as_ptr()).right(),
                            ThreadField::Thread => None,
                        }
                    }
                    Ordering::Equal => break,
                }
            }

            if let Some(mut pnode) = node {
                if (*pnode.as_ptr()).right_field() == ThreadField::Child {
                    // find the successor
                    let mut child = (*pnode.as_ptr()).right().unwrap();
                    while (*child.as_ptr()).left_field() == ThreadField::Child {
                        child = (*child.as_ptr()).left().unwrap();
                    }
                    (*pnode.as_ptr()).set_key((*child.as_ptr()).key());
                    (*pnode.as_ptr()).set_value((*child.as_ptr()).value());
                    pnode = child;
                }

                let garbage = pnode;
                match (*pnode.as_ptr()).parent().is_none() {
                    true => {
                        self.root = (*pnode.as_ptr()).left();
                        self.tail = (*pnode.as_ptr()).left();
                    }
                    false => {
                        let par = (*pnode.as_ptr()).parent().unwrap();
                        if (*par.as_ptr()).left() == Some(pnode) {
                            (*par.as_ptr())
                                .set_left_with_field((*pnode.as_ptr()).left(), ThreadField::Thread);
                            if (*par.as_ptr()).left().is_none() {
                                self.head = Some(par);
                            }
                        } else {
                            (*par.as_ptr()).set_right_with_field(
                                (*pnode.as_ptr()).right(),
                                ThreadField::Thread,
                            );
                            if (*par.as_ptr()).right().is_none() {
                                self.tail = Some(par);
                            }
                        }
                        while let Some(mut parent) = (*pnode.as_ptr()).parent() {
                            // retraverse and update
                            let factor = (*parent.as_ptr()).balance_factor();
                            if (*pnode.as_ptr()).less(parent.as_ref()) {
                                // update balance_factor of left
                                let new_factor = factor + AVLFactor::Plus;
                                (*parent.as_ptr()).update_factor(new_factor);
                                if new_factor == AVLFactor::Plus {
                                    break;
                                } else if new_factor == AVLFactor::PlusPlus {
                                    let rhd = (*parent.as_ptr()).right().unwrap();
                                    let factor_rhd = (*rhd.as_ptr()).balance_factor();
                                    if factor_rhd == AVLFactor::Minus {
                                        let grandson = (*rhd.as_ptr()).left().unwrap();
                                        let factor_gs = (*grandson.as_ptr()).balance_factor();
                                        // rotate right and then left at grandson
                                        (*grandson.as_ptr()).thread_rotate_right();
                                        (*grandson.as_ptr()).thread_rotate_left();
                                        (*grandson.as_ptr()).update_factor(AVLFactor::Zero);
                                        let (fp, fc) = match factor_gs {
                                            AVLFactor::Plus => (AVLFactor::Minus, AVLFactor::Zero),
                                            AVLFactor::Zero => (AVLFactor::Zero, AVLFactor::Zero),
                                            AVLFactor::Minus => (AVLFactor::Zero, AVLFactor::Plus),
                                            _ => panic!("factor is out of bound"),
                                        };
                                        (*parent.as_ptr()).update_factor(fp);
                                        (*rhd.as_ptr()).update_factor(fc);
                                        parent = grandson; // after rotation
                                    } else {
                                        (*rhd.as_ptr()).thread_rotate_left();
                                        if factor_rhd == AVLFactor::Zero {
                                            (*parent.as_ptr()).update_factor(AVLFactor::Plus);
                                            (*rhd.as_ptr()).update_factor(AVLFactor::Minus);
                                            break;
                                        } else {
                                            (*parent.as_ptr()).update_factor(AVLFactor::Zero);
                                            (*rhd.as_ptr()).update_factor(AVLFactor::Zero);
                                            parent = rhd; // after rotation
                                        }
                                    }
                                }
                            } else {
                                // update balance_factor of right
                                let new_factor = factor + AVLFactor::Minus;
                                (*parent.as_ptr()).update_factor(new_factor);
                                if new_factor == AVLFactor::Minus {
                                    break;
                                } else if new_factor == AVLFactor::MinusMinus {
                                    let lhd = (*parent.as_ptr()).left().unwrap();
                                    let factor_lhd = (*lhd.as_ptr()).balance_factor();
                                    if factor_lhd == AVLFactor::Plus {
                                        let grandson = (*lhd.as_ptr()).right().unwrap();
                                        let factor_gs = (*grandson.as_ptr()).balance_factor();
                                        // rotate left and then right at grandson
                                        (*grandson.as_ptr()).thread_rotate_left();
                                        (*grandson.as_ptr()).thread_rotate_right();
                                        (*grandson.as_ptr()).update_factor(AVLFactor::Zero);
                                        let (fp, fc) = match factor_gs {
                                            AVLFactor::Minus => (AVLFactor::Plus, AVLFactor::Zero),
                                            AVLFactor::Zero => (AVLFactor::Zero, AVLFactor::Zero),
                                            AVLFactor::Plus => (AVLFactor::Zero, AVLFactor::Minus),
                                            _ => panic!("factor is out of bound"),
                                        };
                                        (*parent.as_ptr()).update_factor(fp);
                                        (*lhd.as_ptr()).update_factor(fc);
                                        parent = grandson; // after rotation
                                    } else {
                                        (*lhd.as_ptr()).thread_rotate_right();
                                        if factor_lhd == AVLFactor::Zero {
                                            (*parent.as_ptr()).update_factor(AVLFactor::Minus);
                                            (*lhd.as_ptr()).update_factor(AVLFactor::Plus);
                                            break;
                                        } else {
                                            (*parent.as_ptr()).update_factor(AVLFactor::Zero);
                                            (*lhd.as_ptr()).update_factor(AVLFactor::Zero);
                                            parent = lhd; // after rotation
                                        }
                                    }
                                }
                            }
                            pnode = parent;
                        }
                    }
                }
                Box::from_raw(garbage.as_ptr());
                self.size -= 1;
                return true;
            }
            return false;
        }
    }

    #[inline]
    fn update(&mut self, key: K, val: V) {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                match (*ptr.as_ptr()).cmp_with_key(&key) {
                    Ordering::Less => {
                        node = match (*ptr.as_ptr()).left_field() {
                            ThreadField::Child => (*ptr.as_ptr()).left(),
                            ThreadField::Thread => None,
                        }
                    }
                    Ordering::Greater => {
                        node = match (*ptr.as_ptr()).right_field() {
                            ThreadField::Child => (*ptr.as_ptr()).right(),
                            ThreadField::Thread => None,
                        }
                    }
                    Ordering::Equal => break,
                }
            }
            if let Some(pnode) = node {
                (*pnode.as_ptr()).set_value(val);
            }
        }
    }

    #[inline]
    fn query(&self, key: K) -> Option<V> {
        let mut node = self.root;
        unsafe {
            while let Some(ptr) = node {
                match (*ptr.as_ptr()).cmp_with_key(&key) {
                    Ordering::Less => {
                        node = match (*ptr.as_ptr()).left_field() {
                            ThreadField::Child => (*ptr.as_ptr()).left(),
                            ThreadField::Thread => None,
                        }
                    }
                    Ordering::Greater => {
                        node = match (*ptr.as_ptr()).right_field() {
                            ThreadField::Child => (*ptr.as_ptr()).right(),
                            ThreadField::Thread => None,
                        }
                    }
                    Ordering::Equal => break,
                }
            }
            node.map(|node| (*node.as_ptr()).value())
        }
    }

    #[inline]
    fn where_val<F: FnMut(&V) -> bool>(&self, mut f: F) -> Vec<V> {
        unsafe {
            let mut res = Vec::<V>::with_capacity(self.size as usize);
            let mut node = self.head;
            while let Some(pnode) = node {
                let val = (*pnode.as_ptr()).value();
                if f(&val) {
                    res.push(val);
                }
                node = match (*pnode.as_ptr()).right_field() {
                    ThreadField::Thread => (*pnode.as_ptr()).right(),
                    ThreadField::Child => {
                        let mut child = (*pnode.as_ptr()).right().unwrap();
                        while (*child.as_ptr()).left_field() == ThreadField::Child {
                            child = (*child.as_ptr()).left().unwrap();
                        }
                        Some(child)
                    }
                };
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn where_key<F: FnMut(&K) -> bool>(&self, mut f: F) -> Vec<K> {
        unsafe {
            let mut res = Vec::<K>::with_capacity(self.size as usize);
            let mut node = self.head;
            while let Some(pnode) = node {
                let key = (*pnode.as_ptr()).key();
                if f(&key) {
                    res.push(key);
                }
                node = match (*pnode.as_ptr()).right_field() {
                    ThreadField::Thread => (*pnode.as_ptr()).right(),
                    ThreadField::Child => {
                        let mut child = (*pnode.as_ptr()).right().unwrap();
                        while (*child.as_ptr()).left_field() == ThreadField::Child {
                            child = (*child.as_ptr()).left().unwrap();
                        }
                        Some(child)
                    }
                };
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<(K, V)> {
        unsafe {
            let mut res = Vec::<(K, V)>::with_capacity(self.size as usize);
            let mut node = self.head;
            while let Some(pnode) = node {
                res.push(((*pnode.as_ptr()).key(), (*pnode.as_ptr()).value()));
                node = match (*pnode.as_ptr()).right_field() {
                    ThreadField::Thread => (*pnode.as_ptr()).right(),
                    ThreadField::Child => {
                        let mut child = (*pnode.as_ptr()).right().unwrap();
                        while (*child.as_ptr()).left_field() == ThreadField::Child {
                            child = (*child.as_ptr()).left().unwrap();
                        }
                        Some(child)
                    }
                };
            }
            res
        }
    }

    #[inline]
    fn min_key(&self) -> Option<K> {
        self.head.map(|node| unsafe { (*node.as_ptr()).key() })
    }

    #[inline]
    fn min_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        self.root.map(|root| unsafe {
            let mut key = (*root.as_ptr()).key();
            let mut min_val = (*root.as_ptr()).value();
            let mut node = self.head;
            while let Some(pnode) = node {
                let val = (*pnode.as_ptr()).value();
                if min_val > val {
                    min_val = val;
                    key = (*pnode.as_ptr()).key();
                }
                node = match (*pnode.as_ptr()).right_field() {
                    ThreadField::Thread => (*pnode.as_ptr()).right(),
                    ThreadField::Child => {
                        let mut child = (*pnode.as_ptr()).right().unwrap();
                        while (*child.as_ptr()).left_field() == ThreadField::Child {
                            child = (*child.as_ptr()).left().unwrap();
                        }
                        Some(child)
                    }
                };
            }
            key
        })
    }

    #[inline]
    fn max_key(&self) -> Option<K> {
        self.tail.map(|node| unsafe { (*node.as_ptr()).key() })
    }

    #[inline]
    fn max_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        self.root.map(|root| unsafe {
            let mut key = (*root.as_ptr()).key();
            let mut max_val = (*root.as_ptr()).value();
            let mut node = self.head;
            while let Some(pnode) = node {
                let val = (*pnode.as_ptr()).value();
                if max_val < val {
                    max_val = val;
                    key = (*pnode.as_ptr()).key();
                }
                node = match (*pnode.as_ptr()).right_field() {
                    ThreadField::Thread => (*pnode.as_ptr()).right(),
                    ThreadField::Child => {
                        let mut child = (*pnode.as_ptr()).right().unwrap();
                        while (*child.as_ptr()).left_field() == ThreadField::Child {
                            child = (*child.as_ptr()).left().unwrap();
                        }
                        Some(child)
                    }
                };
            }
            key
        })
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]
    fn size(&self) -> usize {
        self.size as usize
    }
}
